令 表示当前已经得到了 个面后的期望次数。
有两种情况:
1.掷出已有的面,概率为
2.掷出新的面 , 概率为
那么有:
边界条件 , 倒推即可。
当然,把上式暴力展开后发现答案为
这其实是一个调和级数,由于精度要求不高 可用公式解决。
#include <cmath>
#include <cstdio>
const double Gamma = 0.577215664901532860606512090082402431042159335;
const int MAXN = 1000;
int t , n;
double Ans;
int main( ) {
scanf("%d",&t);
while( t -- ) {
scanf("%d",&n);
Ans = 0;
if( n <= 50 )
for( int i = 1 ; i <= n ; i ++ ) Ans += 1.0 / i;
else
Ans = log( n ) + Gamma + 1.0 / 2 / n;
printf("%.2f\n", Ans * n );
}
return 0;
}